Google co-founder and CEO Larry Page appeared on Charlie Rose’s talk show Monday night to to talk about goings-on in the internet lands. Inevitably, Rose asked Page about the delicate co-existence that Google maintains with Facebook.

Google and Facebook have played the dueling pianos of the internet for years now, but it seems lately Google’s been taking Facebook to task for being a walled garden – at least when it comes to the social networking’ site’s regard to Google, that is. Page elaborated, “I think it’s unfortunate that Facebook has been pretty closed with their data. We are in the business of searching data and we generally don’t turn it down when it’s offered to us. I think in general we would like to see content made more open.”

In the interview, Page recounts Facebook’s habit of allowing users to import Gmail contacts to find people yet Facebook doesn’t reciprocate the courtesy. Page actually says that Facebook “holds its users hostage.” Yowch.

Google personel haven’t really made any secret over their contempt for Facebook’s hoarding of user information when Facebook’s been crawling Gmail contacts for years. Sergey Brin, Google’s other co-founder, recently told the Guardian that Facebook’s business practices are so restrictive that it hinders the open web and stunts innovation and development.

Page recalled that they told Facebook “we only participate with companies that offer reciprocity… and we’re still waiting”. Asked if they might (reciprocate) in the future, Page commented, “I hope so and I imagine that they will be forced to eventually if they don’t choose to.”

Page also talks with Rose about the legitimacy of a Facebook search engine and what that could mean to Google.

Rose: So are your worried or not worried about Facebook’s competition in search?

Page: It’s something that we take seriously just like we do social media.

Check out the segment below. (For some reason, the sound doesn’t kick in till 0:09, though conveniently right when Rose asks Page about a Facebook search engine. It also cuts out with a few second left, but you’ll still get the beef between the bread.)